package com.fanshuai.algorithms.backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * 子集问题，组合问题
 *
 * 两种回溯方式：
 * 递归每个元素，针对每个元素，都0和1两个分支
 */
public class Combine {
    /**
     * 求数组a的所有子集
     * @param a
     * @return
     */
    public List<List<Integer>> subsets(int[] a) {
        List<List<Integer>> subsets = new ArrayList<>();
        subsets(a, 0, new ArrayList<>(), subsets);
        return subsets;
    }

    private void subsets(int[] a, int level, List<Integer> path, List<List<Integer>> all) {
        if (level == a.length) {
            all.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i <= 1; i++) {
            if (i == 0) {
                subsets(a, level + 1, path, all);
            } else {
                path.add(a[level]);
                subsets(a, level + 1, path, all);
                path.remove(path.size() - 1);
            }
        }
    }

    /**
     * 求[1..n]中数量为k的所有组合
     * @param n
     * @param k
     * @return
     */
    public List<List<Integer>> combine(int n, int k) {
        if (n <= 0 || k > n) {
            return new ArrayList<>();
        }

        List<List<Integer>> all = new ArrayList<>();
        combine(n, k, 1, new ArrayList<>(), all);
        return all;
    }

    private void combine(int n, int k, int index, List<Integer> path, List<List<Integer>> all) {
        if (path.size() == k) {
            all.add(new ArrayList<>(path));
            return;
        }
        if (index > n) {
            return;
        }

        for (int i = 0; i <= 1; i++) {
            if (i == 0) {
                combine(n, k, index + 1, path, all);
            } else {
                path.add(index);
                combine(n, k, index + 1, path, all);
                path.remove(path.size() - 1);
            }
        }
    }
}
